Processor instructions are known that provide for branching in dependence on the value of some parameter stored at a particular location (often in the accumulator of the processor ALU). Processor instructions are also known that provide for a degree of indirection in accessing an element to be handled by the instruction; by this is meant that the location of the target element is not directly specified in the instruction, but instead the instruction specifies a location that holds the address of the location storing the target element. More sophisticated indirection involves pre or post indexing based on a value held in a specific processor register (pre-indexing involves modifying the address specified in the instruction whereas post-indexing involves modifying the address stored in the location specified in the instruction).
In apparatus such as a packet switch, a controlling processor will generally be required to carry out some action based on the value of an input quantity such as a packet destination address. This desired capability can be viewed as a branching operation in which the processor must branch to a required action dependent on the value of the input quantity. Alternatively the desired capability can be likened to an operation involving indirection post-indexed by the value of the input quantity. However, in applications such as controlling a packet switch, the range of possible values of the input quantity may be very large even though only a very limited subset of these values may be of interest. The standard branch instructions or instructions involving indirection cannot cope with this requirement in a compact and simple manner and will generally use a number of memory locations corresponding to the number of possible values of the input quantity.
It is an object of the present invention to provide a compact and flexible way of controlling a processor to selectively access elements in dependence on the value of an input quantity.
As will become apparent below, the present invention achieves this object by employing hashing. Hashing is itself a well known technique by which a relatively long input is transformed into a shorter output. Hashing is used for many different purposes including memory look-up and for forming message authentication codes. A large number of different hashing functions are known.
In order to facilitate an understanding of the present invention, a brief description of hashing as applied to memory look-up will now be given with reference to FIG. 1 of the accompanying drawings. More particularly, in the FIG. 1 arrangement, an input 10 (for example, a 48-bit input) is to be used to retrieve data held in memory 11. In the current example, only a relatively small number of the possible values of the input 10 are of interest (for example, seven values). The memory is provided with a number of locations 12 equal, to or greater than, the number of input values of interest (but less than all possible input values), and the input 10 is applied to a hashing function 13 that transforms the input 10 into a shorter length index 14 matched to the size of the memory (in the current example, this might be a 3-bit index). The hashing function 14 is chosen such that every input value of interest produces a unique value of the index 14 and this latter value is then used to access a corresponding location of the memory 11--this location being that used to store the data that it is desired to associate with the input value concerned.
Of course, many values of the input 10 will give rise to the same index value but it is only desired to register a "hit" (a valid output of data from the memory 11) for the input value of interest that hashes to that index value. Accordingly, along with the data to be output, each memory location stores a check value corresponding to the input value for which that data is valid. When a memory location 12 is accessed, the check value is compared in comparator 15 with the current value of the input 10 and a data valid output 16 is only produced if there is a match. If the check value and input value do not match, a "miss" occurs. In so-called "perfect" hashing where every input value of interest is mapped by the hashing function 13 into its own unique value of index, this is the end of the process; however, it is often more efficient to practice "non-perfect" hashing in which there are some clashes between values of interest. In such cases, various strategies have been devised; for example, the indexed location may give access to a linked list of values of interest associated with that location. Another strategy is to effect "re-hashing" (that is, carrying out a hash retry) generally using a different hash function from that originally employed. Re-hashing strategies may extend to multiple re-hashing attempts each with a different predetermined hash function.